package shujujiegou;

public class RedBlackTree {
    private Node root;

    public Object get(Integer key) {
        Node n = getNode(key);
        if(n == null) {
            System.out.println("获取错误:没有对应的key");
            return null;
        }else {
            return n.value;
        }
    }


    public void add(Integer key, Object value){
        Integer position = selectInsertPosition(key);
        add(key, value, position);
        System.out.println("成功插入:" + key);
    }

    private void add(Integer key, Object value, Integer parentKey){
        Node parent = getNode(parentKey);

        Node n = new Node(key, value, parent);
        if(parent == null && root == null){
            this.root = n;
        }else if(parent == null && root !=null){
            System.out.println("错误:插入节点父节点为null");
            return;
        } else if(key == parent.key) {
            System.out.println("错误:插入节点的key值与其父节点的key值一致");
            return;
        } else if (key < parent.key && parent.leftChild == null) {
            parent.leftChild = n;
        } else if(key > parent.key && parent.rightChild == null){
            parent.rightChild = n;
        }
        //插入后 有可能影响红黑树性质 下面进行修正
        addNode(n);
        setRoot();
    }

    /*
     * 通过对比插入节点的key 返回插入位置的父节点key
     */
    private Integer selectInsertPosition(Integer key){
        Node pointer = this.root;
        if(this.root == null) {
            return null;
        }

        for(;;) {
            if(pointer.key < key) {
                if(pointer.rightChild != null) {
                    pointer = pointer.rightChild;
                } else {
                    return pointer.key;
                }
            } else if(pointer.key > key) {
                if(pointer.leftChild != null) {
                    pointer = pointer.leftChild;
                } else {
                    return pointer.key;
                }
            } else {
                System.out.println("错误:插入节点的key值与其父节点的key值一致");
                return null;
            }
        }

    }




    private void setRoot() {
        getRoot();
    }
    private void addNode(Node n) {
        insert_case1(n);
    }

    //根据 键 删除对应节点
    public void deleteNode(Integer key){
        Node thisNode = getNode(key);

        if(thisNode == null) {
            System.out.println("删除错误:没有对应的key");
            return;
        }
        Node delNode = getLeftChildTreeMaxKeyNode(thisNode);
        swapNodeKeyValue(thisNode, delNode);

        delete_one_child(delNode);
        setRoot();
        System.out.println("成功删除:"+key);
    }

    private void delete_one_child(Node delNode) {
        Node child;
        //判断delNode是否有child
        if(delNode.leftChild == null && delNode.rightChild == null) {

            if(delNode.color == Color.black){
                delete_case1(delNode);
            }
            free(delNode);
            return;
        } else if (delNode.leftChild != null){
            child = delNode.leftChild;
        } else {
            child = delNode.rightChild;
        }
        //交换delNode和child的 键 值
        swapNodeKeyValue(delNode, child);
        free(child);
        //有child的情况
        if(delNode.color == Color.black) {

            if(child.color == Color.black) {
                //两个黑色节点 去掉一个  需要一些操作来补回一个黑色节点
                delete_case1(delNode);
            } else {
                //child是红色 直接去掉不影响平衡
            }
        } else {
            //delNode是红色  child一定是黑色    将delNode变黑 则黑色节点数不变
            delNode.color = Color.black;
        }

    }

    private void free(Node freeNode) {
        if(freeNode.parent==null){
            this.root = null;
        }else if(freeNode == freeNode.parent.leftChild) {
            freeNode.parent.leftChild = null;
        } else {
            freeNode.parent.rightChild = null;
        }
    }

    public void order(){
        System.out.print("先根遍历:");
        preOrder(this.root);
        System.out.println();
        System.out.print("中根遍历:");
        inOrder(this.root);
        System.out.println();
//		System.out.print("后根遍历:");
//		postOrder(this.root);
//		System.out.println();
    }

    public void preOrder(Node root){  //先根遍历
        if(root!=null){
            System.out.print(root.color.toString()+root.key+"-");
            preOrder(root.leftChild);
            preOrder(root.rightChild);
        }
    }

    public void inOrder(Node root) { // 中根遍历
        if (root != null) {
            inOrder(root.leftChild);
            System.out.print(root.color.toString() + root.key + "-");
            inOrder(root.rightChild);
        }
    }

    public void postOrder(Node root) { // 后根遍历
        if (root != null) {
            postOrder(root.leftChild);
            postOrder(root.rightChild);
            System.out.print(root.color.toString() + root.key + "-");
        }
    }


    /*
     * 给经过节点n的补一个黑色节点
     */
    private void delete_case1(Node n) {
        if(n.parent != null) {
            delete_case2(n);
        }
        //情况一:::如果为null 说明n是根   直接结束

    }

    private void delete_case2(Node n) {
        Node s = sibling(n);
        if(s != null && s.color == Color.red) {
            n.parent.color = Color.red;
            s.color = Color.black;
            if(n == n.parent.leftChild) {
                rotate_left(n.parent);
            } else {
                rotate_right(n.parent);
            }
        }
        delete_case3(n);
    }

    private void delete_case3(Node n) {
        Node s = sibling(n);
        //n的父亲、S和S的儿子都是黑色的
        if(		s != null &&
                n.parent.color == Color.black &&
                s.color == Color.black &&
                (s.leftChild == null || s.leftChild.color == Color.black) &&
                (s.rightChild == null || s.rightChild.color == Color.black)	) {
            s.color = Color.red;
            //经过n.parent的节点都缺少一个黑色的节点(去经过)
            delete_case1(n.parent);
        } else {
            delete_case4(n);
        }
    }

    private void delete_case4(Node n) {
        Node s = sibling(n);

        if(s == null){
            n.parent.color = Color.black;
        }
        //S和S的儿子都是黑色，但是N的父亲是红色。
        else if(s.color == Color.black && n.parent.color == Color.red &&
                (s.leftChild == null || s.leftChild.color == Color.black) &&
                (s.rightChild == null || s.rightChild.color == Color.black)) {
            s.color = Color.red;
            n.parent.color = Color.black;
        } else {
            delete_case5(n);
        }
    }

    private void delete_case5(Node n) {
        Node s = sibling(n);
        if(s.color == Color.black) {
            if(n == n.parent.leftChild
                    &&s.leftChild != null
                    &&s.leftChild.color == Color.red
                    &&(s.rightChild == null || s.rightChild.color == Color.black)) {
                s.color = Color.red;
                s.leftChild.color = Color.black;
                rotate_right(s);
            } else if(n == n.parent.rightChild&&(s.leftChild == null || s.leftChild.color == Color.black)
                    &&s.rightChild != null && s.rightChild.color == Color.red) {
                s.color = Color.red;
                s.rightChild.color = Color.black;
                rotate_left(s);
            }
        }
        delete_case6(n);
    }

    private void delete_case6(Node n) {
        Node s = sibling(n);
        s.color = n.parent.color;
        n.parent.color = Color.black;
        if(n == n.parent.leftChild) {
            s.rightChild.color = Color.black;
            rotate_left(n.parent);
        } else {
            s.leftChild.color = Color.black;
            rotate_right(n.parent);
        }
    }

    private Node sibling(Node n) {
        if(n == n.parent.leftChild) {
            return n.parent.rightChild;
        } else {
            return n.parent.leftChild;
        }
    }

    //交换两个节点的 键 值
    private void swapNodeKeyValue(Node thisNode, Node delNode) {
        Integer tkey = thisNode.key;
        thisNode.key = delNode.key;
        delNode.key = tkey;

        Object temp = thisNode.value;
        thisNode.value = delNode.value;
        delNode.value = temp;
    }

    //获取thisNode的左子树里  最大键的节点
    private Node getLeftChildTreeMaxKeyNode(Node thisNode) {
        if(thisNode.leftChild == null){
            return thisNode;
        }
        Node n = thisNode.leftChild;
        while(n.rightChild != null) {
            n = n.rightChild;
        }
        return n;
    }

    //根据 键 获取对应节点
    public Node getNode(Integer key) {
        //获取树的根
        Node n = getRoot();
        for(;;){
            if(n == null) return null;
            if(key.equals(n.key)) {
                return n;
            } else if(key < n.key && n.leftChild !=null) {
                n = n.leftChild;
            } else if(key > n.key && n.rightChild != null) {
                n = n.rightChild;
            } else {
                return null;
            }
        }
    }







    //获取根节点
    private Node getRoot() {
        if(root == null) {
            return root;
        }
        while(this.root.parent != null) {
            this.root = this.root.parent;
        }
        return root;
    }

    private void insert_case1(Node n){
        if(n.parent == null) {
            n.color = Color.black;
        } else {
            insert_case2(n);
        }

    }


    private void insert_case2(Node n) {
        if(n.parent.color == Color.black) {
            return;
        } else {
            insert_case3(n);
        }
    }


    private void insert_case3(Node n) {
        if(n.uncle() != null && n.uncle().color == Color.red) {
            n.parent.color = Color.black;
            n.uncle().color = Color.black;
            n.grandparent().color = Color.red;
            insert_case1(n.grandparent());
        } else {
            insert_case4(n);
        }

    }


    private void insert_case4(Node n) {
        //n是右孩子  父亲是左孩子
        if(n == n.parent.rightChild && n.parent == n.grandparent().leftChild) {
            rotate_left(n.parent);
            n = n.leftChild;
        } else if(n == n.parent.leftChild && n.parent == n.grandparent().rightChild) {
            rotate_right(n.parent);
            n = n.rightChild;
        }
        insert_case5(n);
    }

    private void insert_case5(Node n) {
        n.parent.color = Color.black;
        n.grandparent().color = Color.red;
        if(n == n.parent.leftChild && n.parent == n.grandparent().leftChild) {
            rotate_right(n.grandparent());
        } else {
            rotate_left(n.grandparent());
        }
    }


    /*
     * 左旋转
     */
    private void rotate_left(Node n) {
        Node nParent = n.parent;
        Node nRightChild = n.rightChild;
        Node nRightChildLeftChild = n.rightChild.leftChild;

        if(nParent != null) {
            if(n == nParent.leftChild) {
                nParent.leftChild = nRightChild;
            } else {
                nParent.rightChild = nRightChild;
            }
        }
        nRightChild.parent = nParent;

        nRightChild.leftChild = n;
        n.parent = nRightChild;

        n.rightChild = nRightChildLeftChild;
        if(nRightChildLeftChild != null) {
            nRightChildLeftChild.parent = n;
        }
    }
    /*
     * 右旋转
     */
    private void rotate_right(Node n) {
        Node nParent = n.parent;
        Node nLeftChild = n.leftChild;
        Node nLeftChildRightChild = n.leftChild.rightChild;
        if(nParent != null) {
            if(n == nParent.rightChild) {
                nParent.rightChild = nLeftChild;
            } else {
                nParent.leftChild = nLeftChild;
            }
        }
        nLeftChild.parent = nParent;

        nLeftChild.rightChild = n;
        n.parent = nLeftChild;

        n.leftChild = nLeftChildRightChild;
        if(nLeftChildRightChild != null) {
            nLeftChildRightChild.parent = n;
        }
    }








    class Node {
        private Node grandparent;
        private Node uncle;
        private Node parent;
        private Node leftChild;
        private Node rightChild;
        public Color color;
        private Integer key;
        private Object value;
        public Node(Integer key, Object value, Node parent) {
            this.key = key;
            this.value = value;
            this.parent = parent;
            this.color = Color.red;
            //设置祖父
            if(this.parent != null) {
                grandparent = this.parent.parent;
            }
            //设置叔父
            if(this.grandparent != null) {
                if(this.parent == this.grandparent.leftChild) {
                    uncle = this.grandparent.rightChild;
                } else {
                    uncle = this.grandparent.leftChild;
                }
            }

        }
        public Node grandparent(){
            //设置祖父
            if(this.parent != null) {
                grandparent = this.parent.parent;
            }
            return grandparent;
        }
        public Node uncle(){
            //设置叔父
            if(this.grandparent() != null) {
                if(this.parent == this.grandparent.leftChild) {
                    uncle = this.grandparent.rightChild;
                } else {
                    uncle = this.grandparent.leftChild;
                }
            }
            return uncle;
        }


    }
    public enum Color {
        red("R"),black("B");
        private String c;
        private Color(String c){
            this.c = c;
        }
        @Override
        public String toString() {
            return c;
        }
    }
}
